import java.util.ArrayList;
import java.util.List;

class Solution5 {
    int left;// 记录左括号数量
    int right;// 记录右括号数量
    List<String> ret;// 返回结果
    StringBuffer path;// 记录当前路径
    int N;

    public List<String> generateParenthesis(int n) {
        left = 0;
        right = 0;
        ret = new ArrayList<>();
        path = new StringBuffer();
        N = n;
        dfs();
        return ret;
    }

    public void dfs() {
        if (right == N) {
            // 递归出口
            ret.add(path.toString());
            return;
        }

        if (left < N) {
            // 添加左括号
            left++;
            path.append('(');
            dfs();// 进入下一层
            left--;// 回溯
            path.deleteCharAt(path.length() - 1);
        }
        if (right < left) {
            // 添加右括号
            right++;
            path.append(')');
            dfs();// 进入下一层
            right--;// 回溯
            path.deleteCharAt(path.length() - 1);
        }
    }

}